/*
 * @Author: 缄默
 * @Date: 2021-10-27 17:20:52
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-11 21:28:57
 */
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;

//定义树的结构 初始化树
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode() : val(0), left(nullptr), right(nullptr) {}

};

//根据树的先序遍历和中序遍历实现树的构建
TreeNode *buildTree(vector<int> &preOrder, vector<int> &inOrder, int rootIndex, int left, int right)
{
    
    if (left > right)
        return nullptr;
    TreeNode *root = new TreeNode(preOrder[rootIndex]);
    int index = left;
    while (index < right && preOrder[rootIndex] != inOrder[index])
    {
        index++;
    }
    //划分的是中序遍历的数组
    //第一个参数传递的是子树的根节点在先序遍历的位置
    root->left = buildTree(preOrder, inOrder, rootIndex + 1, left, index - 1);
    //根节点的右子树的位置在根节点的位置+左子树的长度+1  左子树的长度为中序遍历中根节点减去左边界
    root->right = buildTree(preOrder, inOrder, rootIndex + index - left + 1, index + 1, right);
    return root;
}
//先序遍历树
void prePrint(TreeNode *root)
{
    if (root == nullptr)
    {
        cout << "null"
             << " ";
    }
    else
    {
        cout << root->val << "  ";
        prePrint(root->left);
        prePrint(root->right);
    }
}
//中序遍历树
void inPrint(TreeNode *root)
{
    if (root == nullptr)
    {
        cout << "null"
             << " ";
        return;
    }
    else
    {
        inPrint(root->left);
        cout << root->val << "  ";
        inPrint(root->right);
    }
    return;
}
//广度优先搜索遍历树
void BFS(TreeNode *root)
{
    queue<TreeNode *> que;
    que.push(root);
    while (!que.empty())
    {
        TreeNode *tree = que.front();
        que.pop();
        if (tree == nullptr)
        {
            cout << "null"
                 << " ";
        }
        else
        {
            que.push(tree->left);
            que.push(tree->right);
            cout << tree->val << "  ";
        }
    }
}
//深度优先搜索遍历树
void DFS(TreeNode *root)
{
    stack<TreeNode *> sta;
    sta.push(root);
    while (!sta.empty())
    {
        TreeNode *tree = sta.top();
        sta.pop();
        if (tree == nullptr)
        {
            cout << "null"
                 << " ";
        }
        else
        {
            sta.push(tree->right);
            sta.push(tree->left);
            cout << tree->val << "  ";
        }
    }
}
//直观的打印二叉树
void printTree(TreeNode* root) {
    
}


TreeNode* buildTreeByArray(vector<int>& arr) {
    if (arr.size() == 0) return new TreeNode();
    TreeNode* head = new TreeNode(arr[0]);
    TreeNode* node;
    int i = 1;
    queue<TreeNode*> que;
    que.push(head);
    
    while (!que.empty()) {
    TreeNode* node = que.front();
    que.pop();
    node->left = new TreeNode(arr[i++]);
    if (i == arr.size()) break;
    node->right = new TreeNode(arr[i++]);
    if (i == arr.size()) break;
    que.push(node->left);
    que.push(node->right);
    }
    return head;
    
}

int max(int a, int b) {
    return a < b ? b : a;
}
//树的深度优先搜索与树的先序遍历相同 下面采用堆栈和非递归方式实现


